package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhanBo
 * @date 2020/5/27
 */
public class Solution35 {

    public static void main(String[] args) {
        Node node1 = new Node(7);
        Node node2 = new Node(13);
        Node node3 = new Node(11);
        Node node4 = new Node(10);
        Node node5 = new Node(1);
        node1.next =node2;
        node1.random =null;
        node2.next =node3;
        node2.random =node1;
        node3.next=node4;
        node3.random = node5;
        node4.next = node5;
        node4.random = node3;
        node5.next =null;
        node5.random = node1;
        copyRandomList(node1);

    }


    /**
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     *
     * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
     * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
     *
     * 输入：head = [[3,null],[3,0],[3,null]]
     * 输出：[[3,null],[3,0],[3,null]]
     *
     * 输入：head = []
     * 输出：[]
     * 解释：给定的链表为空（空指针），因此返回 null。
     *
     */
    public static Node copyRandomList(Node head) {
        // 使用哈希
        // 哈希表中<原表节点，新表节点>
        Map<Node,Node> map=new HashMap<>(16);
        Node p=head;
        while(p!=null){
            map.put(p,new Node(p.val));
            p=p.next;
        }
        p=head;
        while(p!=null){
            map.get(p).next=map.get(p.next);
            map.get(p).random=map.get(p.random);
            p=p.next;
        }
        return map.get(head);
    }


}
